# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/5 19:10 
"""

"""
顺序查找法不成功的情况下的时间复杂度为O(n)
二分查找的时间度为O(log2(n))
"""

def binary_search(L, val):
    """
    对于有序查找表的二分查找算法的时间复杂度算法
    Args:
        L:
        val:

    Returns:

    """
    low, high = 0, len(L) - 1
    count = 0
    while low <=high:
        mid = (low + high) // 2
        if L[mid] == val:
            return mid
        elif L[mid] > val:
            high = mid - 1
        elif L[mid] < val:
            low = mid + 1
        count += 1
        print(low, high, mid,count)
    print('1 count:', count)
    return False


def binary_search2(L, val):
    """
    对于有序查找表的二分查找算法的时间复杂度算法
    Args:
        L:
        val:

    Returns:

    """
    low, high = 0, len(L)-1
    count = 0
    while low < high:
        mid = low + (high - low)// 2
        if L[mid] == val:
            return mid
        elif L[mid] > val:
            high = mid - 1
        elif L[mid] < val:
            low = mid + 1
        count += 1
        print(low, high, count)
    print('2:count:', count)
    return False


def binary_search3(List,val):
    """
    插值搜索
    Args:
        List:
        val:

    Returns:

    """
    low,high=0,len(List)-1
    count=0
    while low<high:
        mid=low+int((val-List[low])/(List[high]-List[low])*(high-low))
        if val==List[mid]:
            return mid
        elif val>List[mid]:
            low=mid+1
        elif val<List[mid]:
            high=mid-1
        count+=1
        print('inter count:',count)
    return False

"""
插值法适用于关键字分布比较均匀的查找表
查找成功或失败的时间复杂度均为O(log2(log2n))
"""


if __name__ == '__main__':
    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444,555,789]
    result1 = binary_search(LIST, 99)
    # print(result1)
    result2 = binary_search2(LIST, 99)
    print(result1, result2)

    result3 = binary_search3(LIST, 99)
    print(result3)